// https://www.lintcode.com/problem/digital-flip/my-submissions

class Solution {
public:
    /**
     * @param nums: the array
     * @return: the minimum times to flip digit
     */
    // 法一：动态规划：需要知道前一位是0还是1，不知道对信息加入状态里！
    // int flipDigit(vector<int> &nums) {
    //     int n = nums.size();
    //     vector<vector<int>> result(n + 1, vector<int>(2, 0));
    //     result[0][0] = 0;
    //     result[0][1] = 0;
    //     // for (int i = 1; i < n + 1; ++i)
    //     // {
    //     //     if (nums[i - 1] == 1)
    //     //     {
    //     //         result[i][0] = min(result[i - 1][0], result[i - 1][1]) + 1;
    //     //         result[i][1] = result[i - 1][1];
    //     //     }
    //     //     else
    //     //     {
    //     //         result[i][0] = min(result[i - 1][0], result[i - 1][1]);
    //     //         result[i][1] = result[i - 1][1] + 1;
    //     //     }
    //     // }
        
    //     // 根据转移公式来写
    //     for (int i = 1; i < n + 1; ++i)
    //     {
    //         for (int j = 0; j < 2; ++j)
    //         {
    //             result[i][j] = INT_MAX;
    //             int t = 0;
    //             if (j != nums[i - 1])
    //                 t = 1;
    //             for (int k = 0; k < 2; ++k)
    //             {
    //                 if (k == 0 && j == 1)
    //                     continue;
    //                 result[i][j] = min(result[i][j], result[i - 1][k] + t);
    //             }
    //         }
    //     }
        
    //     return min(result[n][0], result[n][1]);
    // }
    
    // 滚动数组优化（一维变成两个变量）
    // int flipDigit(vector<int> &nums) {
    //     int n = nums.size();
    //     int zeroRec = 0;
    //     int oneRec = 0;
    //     for (int i = 0; i < nums.size(); ++i)
    //     {
    //         int zeroTmp = 0;
    //         int oneTmp = 0;
    //         if (nums[i] == 0)
    //         {
    //             oneTmp = oneRec + 1;
    //             zeroTmp = min(zeroRec, oneRec);
    //         }
    //         else
    //         {
    //             oneTmp = oneRec;
    //             zeroTmp = min(zeroRec, oneRec) + 1;
    //         }
    //         zeroRec = zeroTmp;
    //         oneRec = oneTmp;
    //     }
    //     return min(oneRec, zeroRec);
    // }    
    
    // 进一步简化
    // int flipDigit(vector<int> &nums) {
    //     int n = nums.size();
    //     int zeroRec = 0;
    //     int oneRec = 0;
    //     for (int i = 0; i < nums.size(); ++i)
    //     {
    //         zeroRec = min(zeroRec, oneRec); //为0的代价，不管前一个是0还是1，这一个都可以为0
                // 另一个角度：0的话，可以把前面都翻转为1也可以都翻转为0，看哪个次数少！！！
    //         if (nums[i] == 0)
    //             oneRec++;
    //         else
    //             zeroRec++;
    //     }
    //     return min(oneRec, zeroRec);
    // }    
    
    
    // 法二：记录
    // 另一个角度：1的话，可以把后面都翻转为1也可以都翻转为0，看哪个次数少！！！
    int flipDigit(vector<int> &nums) {
    int all = 0, temp = 0, ans = nums.size();
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == 1) {
                all++;
            }
        }
        ans = all;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == 1) { // 如果当前是1，后面是0还是1都行
                temp++;
            }
            ans = min(ans, all - temp + i - temp + 1); //左边0翻转为1，右边1翻转为0
        }
        return ans;
    }
};